package com.sort;

/**
 * @author zsj
 * @version 1.0
 * @date 2024/5/25 16:02
 * @description 归并排序
 */
public class MergeSortDemo {

    /*
     * 归并排序的思路
     * 定义一个mid点
     * 将mid左边的数据排序(包含mid)
     * 将mid右边的数据排序(不包含mid)
     * 排好这两边的序后 根据mid点使用双指针对数据进行合并
     * 最后得到有序数组
     * 合并细节：
        定义一个temp数组和index索引从0开始
        左指针从0开始 右指针从mid+1开始
        如果左指针小于或者等于右指针的值
        temp[index++] = arr[left++];
        如果左指针大于右指针的值
        temp[index++] =arr[right++];
        最后定义两个循环 如果左指针或者右指针有越界情况
        将剩余的元素依次添加到temp中即可(白话：可能存在没有添加完有一边的数据还有残留 将残留的数据添加到temp数组中)
        最后对arr从新进行一次赋值即可
     */
    public static void main(String[] args) {
        int[] arr = {3, 2, 1, 5, 6, 2};
        System.out.println(smallSum(arr));
        process(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void process(int[] arr, int left, int right) {
        if (left == right) return;
        //定义mid
        int mid = left + ((right - left) >> 1);

        //排序左边界
        process(arr, left, mid);

        //排序右边界
        process(arr, mid + 1, right);

        //最后将两边的数据合并
        merge(arr, left, right, mid);
    }

    private static void merge(int[] arr, int left, int right, int mid) {
        //定义两个指针
        int p1 = left, p2 = mid + 1, b = 0;
        //定义一个temp数组和初始索引
        int[] temp = new int[right - left + 1];
        //开始合并
        //保证p1不超过mid  p2不超过right
        while (p1 <= mid && p2 <= right) {
            temp[b++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        //处理剩余数据
        while (p1 <= mid) {
            temp[b++] = arr[p1++];
        }
        while (p2 <= right) {
            temp[b++] = arr[p2++];
        }
        //将arr赋值给新数组
        for (int i = 0; i < temp.length; i++) {
            arr[left + i] = temp[i];
        }
    }


    //小和问题  求一个数的左边比它小的数字和 并且汇总每一位数字的小和

    /*
      思路 暴力就不说了
      有个思想
      我们求一个数左边有多少个比它小的
      可以转换为右边有多少个比它大的 假设当前这个数为n 如果右边有两个比它大的值
      我们就可以得到一个小和 为2n
      依次遍历

      优化 ：我们使用归并的思想对算法进行优化
      在每次归并的时候
      我们会得到这些数据的每个分界点
       比如我们有数据集为{1,3,4,2,5}
           13425
           /   \
         134   25
        /  \   / \
      13   4  2   5
      / \
     1  3
     ↑   ↑
     p1  p2
      这样我们又是双指针p1 和p2
      我们每次比较
        如果左边的数字比右边的数字小
        那么我们就可以得到右边数据量的个数的左边数字的小和
        像上面我们就可以得到1个1
        (举个列子  如果数据是这样的
           左边的数据是1   右边的数据是2和3
           那么我们就可以得到2个1的小和 因为1比右边的数据小 并且右边的数据有两个
            第一次是1和2对比 temp ={1} 并且收集两个1
            第二次p1越界 将temp = {1,2,3}
        )
     */

    public static int smallSum(int[] arr) {
        if (arr == null || arr.length < 2) return 0;
        //左排序
        //右边排序
        //合并  在合并的过程中统计小和的个数并且汇总
        return fun(arr, 0, arr.length - 1);
    }

    private static int fun(int[] arr, int l, int r) {
        if (l == r) return 0;
        int mid = l + ((r - l) >> 1);
        return fun(arr, l, mid) +
                fun(arr, mid + 1, r)
                + merge_small_sum(arr, l, r, mid);
    }

    private static int merge_small_sum(int[] arr, int l, int r, int mid) {
        int[] temp = new int[r - l + 1];
        int p1 = l, p2 = mid + 1, b = 0, res = 0;
        while (p1 <= mid && p2 <= r) {
            //就这里添加一个汇总数据条件
            //如果左指针的值小于右指针的值 我们添加右边数据量的左指针的值
            //(r - p2+1) 得到右边数据量
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            //这里的条件也要变换 两个值如果相等的话 我们需要取右边的值下去
            temp[b++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            temp[b++] = arr[p1++];
        }
        while (p2 <= r) {
            temp[b++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[l + i] = temp[i];
        }
        return res;

    }

}
